public class Solution {
    private int[] nums;
    private int[][] dp;

    private int dfs(int i, int j) {
        if (dp[i][j] > 0) return dp[i][j];
        int maxans = 0;
        for (int k = i + 1; k < j; k++) {
            maxans = Math.max(maxans, nums[i] * nums[k] * nums[j] + dfs(i, k) + dfs(k, j));
        }
        return dp[i][j] = maxans;
    }

    public int maxCoins(int[] nums) {
        this.nums = new int[nums.length + 2];
        this.dp = new int[nums.length + 2][nums.length + 2];
        System.arraycopy(nums, 0, this.nums, 1, nums.length);
        this.nums[0] = 1;
        this.nums[nums.length + 1] = 1;
        return dfs(0, nums.length + 1);
    }
}